A palynological analysis of the Upper Paleogene and Neogene deposits in the south of Western Siberia has shown that the spore-pollen spectra have pollen of the genus Decodon J.F. Gmelin (Lythraceae), previously unknown in this region. A new species, Decodon kulundinensis Kuzmina sp. nov., is described based on pollen, and a comparative analysis of the identified pollen with the pollen of the extent Decodon verticillatus (L.) Elliot and with fossil pollen of the genus Decodon from Cenozoic deposits of North America, Europe, and China is provided. The dispersal of D. kulundinensis pollen is traced in the Oligocene and Miocene of the south of West Siberian Plain. Single specimens are recorded in the Novaya Mikhailovka Formation (Lower Oligocene), such pollen is also found in the Zhuravka (Upper Oligocene) and Abrosimovka (Lower Miocene) formations, and its highest counts are obtained from the Bescheul Formation (Lower-Middle Miocene); such pollen is already absent in Upper Miocene deposits.